package main.Q601_700;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Q671_680 {
    public static void main(String[] args) {
        System.out.println("Question671：二叉树中第二小的节点");
        System.out.println("Question672：");
        System.out.println("Question673：最长递增子序列的个数");
        int[] arr={1,3,5,4,7};
        System.out.println(new Question673().findNumberOfLIS(arr));
        System.out.println("Question674：最长连续递增序列");
        System.out.println("Question675：");
        System.out.println("Question676：实现一个魔法字典");
        System.out.println("Question677：键值映射");
        System.out.println("Question678：有效的括号字符串");
        System.out.println("Question679：");
        System.out.println("Question680：验证回文串Ⅱ");
    }
}

class Question671{
    public int findSecondMinimumValue(TreeNode root) {
        int min=root.val,secondMin=min;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode curNode=queue.poll();
            if (curNode.val<min){
                secondMin=min;
                min=curNode.val;
            }else if ((curNode.val>min&&curNode.val<secondMin)||(secondMin==min)) secondMin=curNode.val;
            if (curNode.left!=null) queue.add(curNode.left);
            if (curNode.right!=null) queue.add(curNode.right);
        }
        if (min==secondMin) return -1;
        else return secondMin;
    }
}

class Question673{
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        for(int i = 0; i < dp.length; i++) dp[i] = 1;
        int[] count = new int[nums.length];
        for(int i = 0; i < count.length; i++) count[i] = 1;
        int maxCount = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
                if (dp[i] > maxCount) maxCount = dp[i];
            }
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }
}

class Question674{
    public static int findLengthOfLCIS(int[] nums) {//滑动窗口
        int left=0,right=0,maxLength=0;
        while (right< nums.length){
            if (right+1< nums.length&&nums[right+1]>nums[right]) right++;
            else if (right+1< nums.length&&nums[right+1]<=nums[right]){
                left=right+1;
                right=left;
            }
            maxLength=Math.max(maxLength,right-left+1);
            if (right== nums.length-1) break;
        }
        return maxLength;
    }
}

class Question676{
    String[] words;
    public Question676() {
        words=null;
    }

    public void buildDict(String[] dictionary) {
        words=dictionary;
    }

    public boolean search(String searchWord) {
        for (String word:words){
            if (word.length()==searchWord.length()){
                if (process(word,searchWord)) return true;
            }
        }
        return false;
    }

    public boolean process(String str1,String str2){
        char[] s1=str1.toCharArray(),s2=str2.toCharArray();
        int i=0,count=0;
        while (i<s1.length){
            if (s1[i]!=s2[i]) count++;
            if (count>1) return false;
            i++;
        }
        if (count==1) return true;
        else return false;
    }
}

class Question677{
    Map<String,Integer> map;
    /** Initialize your data structure here. */
    public Question677() {
        map=new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        int count=0;
        for (String words: map.keySet()){
            if (words.length()>=prefix.length()&&prefix.equals(words.substring(0,prefix.length()))) {
                count+=map.get(words);
            }
        }
        return count;
    }
}

class Question678{
    public boolean checkValidString(String s) {
        StringBuffer validStr=new StringBuffer();
        char[] str=s.toCharArray();

        return false;
    }
}

class Question680{
    public boolean process(char[] str,int low,int high){
        while (low<=high){
            if (str[low]!=str[high]) return false;
            low++;
            high--;
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        char[] str=s.toCharArray();
        int low=0,high= str.length-1;
        while (low<=high){
            if (process(str,low,high)) return true;
            if (str[low]==str[high]){//两边相等
                low++;
                high--;
            }else {//两边不等
                if (process(str,low+1,high)) return true;
                else if (process(str,low,high-1)) return true;
                else return false;
            }
        }
        return false;
    }
}